/*
  [BCSP-X 2024 12 月小学高年级组] 质数补全
  题目描述
    Alice 在纸条上写了一个质数，第二天再看时发现有些地方污损看不清了。
    在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数称为质数。
    请你帮助 Alice 补全这个质数，若有多解输出数值最小的，若无解输出 −1。

    例如: 纸条上的数字为 1∗（∗ 代表看不清的地方），那么这个质数有可能为 11,13,17,19，其中最小的为 11。
  输入格式
    第一行 1 个整数 t，代表有 t 组数据。
    接下来 t 行，每行 1 个字符串 s 代表 Alice 的数字，仅包含数字或者 ∗，并且保证首位不是 ∗ 或者 0。
  输出格式
    输出 t 行，每行 1 个整数代表最小可能的质数，或者 −1 代表无解。
  输入输出样例
    输入 #1
      10
      1*
      3**
      7**
      83*7
      2262
      6**1
      29*7
      889*
      777*
      225*
    输出 #1
      11
      307
      701
      8317
      -1
      6011
      2917
      8893
      -1
      2251
    输入 #2
      10
      4039***
      2***5*5
      4099961
      25**757
      7***0**
      1***00*
      41811*9
      6***0*7
      8***1**
      6561*59
    输出 #2
      4039019
      -1
      4099961
      2509757
      7000003
      1000003
      4181129
      6000047
      8000101
      6561259
  说明/提示
    样例 3-6
      参考附件中的样例。

  数据范围
    ∣s∣ 代表 s 串的长度，对于所有数据，1 ≤ t ≤ 10, 1 ≤ ∣s∣ ≤ 7，s 中仅包含数字或者 ∗，并且保证首位不是 ∗ 或者 0。

    本题采用捆绑测试，你必须通过子任务中的所有数据点以及其依赖的子任务，才能获得子任务对应的分数。
      子任务编号    分值    ∣s∣    特殊性质               子任务依赖
          1        35      ≤ 7    s 中没有 ∗
          2        30      ≤ 4
          3        24      ≤ 7    s 中至多包含 1 个 ∗         1
          4        11      ≤ 7                            1, 2, 3
*/

#include <bits/stdc++.h>

using namespace std;

/*
  思路:
    1) 由于题目中明确每个待补全的数字最多有 7 位 (1 ≤ ∣s∣ ≤ 7), 也就是这个数最大也小于 10^7,
       我们可以先用线性筛法求出 1 ~ 10^7 范围内的所有质数, 并按从小到大的数序放到全局数组 b 中!
    2) 对于每一个待补全的数 s, 查找和它匹配的最小质数的方法:
         从小到大遍历数组 b 中的每个数 b[i], 看 s 是否和其匹配，
           如果匹配，则说明 b[i] 即为 s 对应的满足条件的最小质数!
           如果不匹配，则继续找 b 中的其它数;
           如果遍历完数据 b 中的所有数，都没有找到和 s 匹配的数，则说明无解!
         其中, 判断 s 和质数 b[i] 是否匹配的方法:
           a) 使用 to_string() 函数将质数 b[i] 转换成 string变量 a1；
           b) 判断 s 和 a1 是否匹配的方法:
              i).  如果 s 和 a1 的字符串长度不相同, 则它们一定不匹配;
              ii). 对 string变量 s 和 a1 的每个相同位置的字符进行比较，
                   如果有字符不等且不等于 "*"，则它们一定不匹配;
                   比较完所有相同位置的字符后，没有发现不匹配，则说明 s 和 a1 匹配；
                   即 s 和 b[i] 匹配!
*/

bool a[10000001] = {1, 1};
int b[10000001] = {};
string s;

/*
 该函数用来判定 string类型的全局变量 s 和 输入参数 a1 是否匹配.
 返回值取值范围为 true/false. 其中，true: s 和 a1 匹配； false: s 和 a1 不匹配
 */
bool cmp(string a1) {
    if (a1.size() != s.size()) {
        return false;
    } else {
        for (int i = 0; i < s.size(); i++) {
            if (a1[i] != s[i] && s[i] != '*') {
                return false;
            }
        }
        return true;
    }
}

int main() {

    // 用线性筛法求出 1 ~ 10^7 之间的所有质数, 并将其按从小到大的数序放到全局数组 b 中
    int sum = 0;
    for (int i = 2; i <= 10000000; i++) {
        if (a[i] == 0) {
            b[sum++] = i;
        }
        for (int j = 0; j < sum; j++) {
            if (i * b[j] <= 10000000) {
                a[b[j] * i] = 1;
            } else {
                break;
            }
            if (i % b[j] == 0) {
                break;
            }
        }
    }

    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        bool ans1 = false;

        /*
          对于待补全的数 s，查找和其匹配的最小质数.
          查找方法：
            从小到大遍历数组 b 中的数 b[i], 看 s 是否和其匹配，
              如果匹配，则说明 b[i] 即为 s 对应的满足条件的最小质数!
              如果不匹配，则继续看 b 中的其它数是否和 s 匹配;
              如果遍历完数据 b 中的所有数，都没有找到和 s 匹配的数，则说明无解!
        */
        cin >> s;
        for (int j = 0; j < sum; j++) {
            string a1 = to_string(b[j]); // 注意: 这里使用了 to_string() 函数将整数 b[j] 转换成 string类型变量 a1
            if (cmp(a1)) { // 如果 a1 和 s 匹配，则说明 a1 即为要找最小质数
                cout << a1 << endl;
                ans1 = true;
                break;
            }
        }
        if (ans1 != true) { // 遍历完数据 b 中的所有数，没有找到和 s 匹配的数，说明无解!
            cout << -1 << endl;
        }
    }

    return 0;
}